#include "rbtree_option.h"

static struct rbtreeNodeCommonInform *rbtreeFindNodeCommon(struct rbtreeManagerStruct *rbmng, const void *findkey, int keysize)
{
    if (!rbmng || !rbmng->cmpfunc)
    {
        logerror("");
        return NULL;
    }
    struct rb_node *tempnode = rbmng->rbroot.rb_node;
    while (tempnode)
    {
        struct rbtreeNodeCommonInform *tmpUserNode = rb_entry(tempnode, struct rbtreeNodeCommonInform, node);
        int cmpFlag = rbmng->cmpfunc(findkey, keysize, tmpUserNode->rbkey, tmpUserNode->keysize);
        if (cmpFlag == 0)
        {
            return tmpUserNode;
        }
        else if (cmpFlag > 0)
        {
            tempnode = tempnode->rb_right;
        }
        else if (cmpFlag < 0)
        {
            tempnode = tempnode->rb_left;
        }
    }
    return NULL;
}
static struct rbtreeNodeCommonInform *rbtreeGetRootInform(struct rbtreeManagerStruct *rbmng)
{
    if (!rbmng || !rbmng->cmpfunc)
    {
        logerror("");
        return NULL;
    }
    struct rbtreeNodeCommonInform *tmpUserNode = rb_entry(rbmng->rbroot.rb_node, struct rbtreeNodeCommonInform, node);
    return tmpUserNode;
}

static int rbtreeAllocKeyData(struct rbtreeNodeCommonInform *optinform, const void *inkey, uint32_t keysize)
{
    if (!optinform)
    {
        logerror("optinform is null");
        return -1;
    }
    if (keysize > 0)
    {
        if (!inkey)
        {
            logerror("pointer is null and size > 0");
            return -1;
        }
        if (optinform->keysize > 0 && optinform->rbkey)
        {
            free(optinform->rbkey);
        }
        optinform->rbkey = malloc(keysize);
        if (!optinform->rbkey)
        {
            logerror("rbtreeNodeCommonInform alloc error");
            return -1;
        }
        memcpy(optinform->rbkey, inkey, keysize);
        optinform->keysize = keysize;
    }
    else
    {
        optinform->rbkey = (void *)inkey;
        optinform->keysize = 0;
    }
    return 1;
}

// keysize如果是字符串，需要包括字符串结束符号。
static int rbtreeRootInsertCommon(struct rbtreeManagerStruct *rbmng, const void *inkey, int keysize, void *indata, uint32_t datasize)
{
    if (!rbmng || !rbmng->cmpfunc)
    {
        logerror("");
        return -1;
    }
    struct rb_node **insertNodePointer = &rbmng->rbroot.rb_node, *parent = NULL;
    struct rbtreeNodeCommonInform *tmpInsertNode = malloc(sizeof(struct rbtreeNodeCommonInform));
    if (!tmpInsertNode)
    {
        logerror("rbtreeNodeCommonInform alloc error");
        goto errorPointor;
    }
    if (rbtreeAllocKeyData(tmpInsertNode, inkey, keysize) < 0)
    {
        logerror("rbtreeAllocKeyData alloc error");
        goto errorPointor;
    }
    while (*insertNodePointer)
    {
        parent = *insertNodePointer;
        struct rbtreeNodeCommonInform *tmpUserNode = rb_entry(parent, struct rbtreeNodeCommonInform, node);
        int cmpFlag = rbmng->cmpfunc(inkey, keysize, tmpUserNode->rbkey, tmpUserNode->keysize);
        if (cmpFlag < 0)
        {
            insertNodePointer = &parent->rb_left;
        }
        else if (cmpFlag > 0)
        {
            insertNodePointer = &parent->rb_right;
        }
        else
        {
            logerror("insert error");
            goto errorPointor;
        }
    }
    tmpInsertNode->rbval = indata;
    tmpInsertNode->valsize = datasize;
    rb_link_node(&tmpInsertNode->node, parent, insertNodePointer);
    rb_insert_color(&tmpInsertNode->node, &rbmng->rbroot);
    return 1;
errorPointor:
    if (tmpInsertNode && tmpInsertNode->rbkey && tmpInsertNode->keysize > 0)
    {
        free(tmpInsertNode->rbkey);
    }
    if (tmpInsertNode)
    {
        free(tmpInsertNode);
    }
    return -1;
}
static int rbtreeCommonInformFree(struct rbtreeNodeCommonInform *optNodeInform)
{
    if (!optNodeInform)
    {
        logerror("");
        return -1;
    }
    // 不要释放用户数据。
    // if (optNodeInform->valsize > 0 && optNodeInform->rbval)
    // {
    //     free(optNodeInform->rbval);
    // }
    if (optNodeInform->keysize > 0 && optNodeInform->rbkey)
    {
        free(optNodeInform->rbkey);
    }
    free(optNodeInform);
    return 1;
}
static int rbtreeGetDataAndEraseCommon(struct rbtreeManagerStruct *rbmng, struct rbtreeNodeCommonInform *optNodeInform,
                                       void **outvalue, uint32_t *outsize, int eraseflag)
{
    if (!rbmng)
    {
        logerror("");
        return -1;
    }
    if (!optNodeInform)
    {
        return 0;
    }
    if (!outvalue || !outsize)
    {
        logerror("");
        return -1;
    }
    outvalue[0] = optNodeInform->rbval;
    outsize[0] = optNodeInform->valsize;
    if (!eraseflag)
    {
        return 1;
    }
    rb_erase(&optNodeInform->node, &rbmng->rbroot);
    rbtreeCommonInformFree(optNodeInform);
    return 1;
}
static struct rbtreeNodeCommonInform *rbtreeGetLRLimitInform(struct rbtreeManagerStruct *rbmng, int leftLimitFlag)
{
    if (!rbmng || !rbmng->cmpfunc)
    {
        logerror("");
        return NULL;
    }
    struct rb_node *tempNode = rbmng->rbroot.rb_node;
    struct rbtreeNodeCommonInform *tempFindData = NULL;
    while (tempNode)
    {
        struct rb_node *tempChildNode;
        if (leftLimitFlag)
        {
            tempChildNode = tempNode->rb_left;
        }
        else
        {
            tempChildNode = tempNode->rb_right;
        }
        if (tempChildNode)
        {
            tempNode = tempChildNode;
        }
        else
        {
            tempFindData = container_of(tempNode, struct rbtreeNodeCommonInform, node);
            break;
        }
    }
    return tempFindData;
}

// 初始化管理器，需要二叉树比较函数，遍历二叉树的回调函数。
//  setcmp：比较函数
//  settraversal:遍历回调
//  setAutoFree:自动释放
int rbtreeRootInit(struct rbtreeManagerStruct *rbmng, rbCompareFunctionType setcmp, rbTraversalFunctionType settraversal)
{
    if (!rbmng || !setcmp)
    {
        logerror("");
        return -1;
    }
    rbmng->rbroot = RB_ROOT;
    rbmng->cmpfunc = setcmp;
    rbmng->traversalfunc = settraversal;
    pthread_mutex_init(&rbmng->rbtreelock, NULL);
    return 0;
}

// 释放管理器，如果二叉树有数据，无法释放，
// 需要用rbtreeGetRootWithErase删除根节点，并释放用户数据, 直到二叉树为空。
// 二叉树为空，再操作释放管理器。
// 返回0成功，-1失败。
int rbtreeRootFree(struct rbtreeManagerStruct *rbmng)
{
    if (!rbmng)
    {
        logerror("");
        return -1;
    }
    if (rbmng->rbroot.rb_node)
    {
        logerror("has data");
        return -1;
    }
    pthread_mutex_destroy(&rbmng->rbtreelock);
    return 0;
}

// 替换数据后，将旧的用户数据返回，让其释放。
// 替换某个关键字的用户数据。
// inkey是查找的关键字，找到将用户数据替换，没有找到插入。
// invalue是用户分配的数据
// oldval如果替换成功，将旧的用户数据地址返回，让用户释放。
// 返回：-1错误，1成功。----------------->如果插入失败，需要释放用户数据。
int rbtreeInsertOperate(struct rbtreeManagerStruct *rbmng, const void *inkey, int keysize, void *indata, uint32_t datasize)
{
    if (!rbmng || !rbmng->cmpfunc)
    {
        logerror("");
        return -1;
    }
    struct rbtreeNodeCommonInform *tempFindData = rbtreeFindNodeCommon(rbmng, inkey, keysize);
    if (tempFindData)
    {
        logerror("key is in tree");
        return -1;
    }
    return rbtreeRootInsertCommon(rbmng, inkey, keysize, indata, datasize);
}

// 替换数据后，将旧的用户数据返回，让其释放。
// 替换某个关键字的用户数据。
// inkey是查找的关键字，找到将用户数据替换，没有找到插入。
// invalue是用户分配的数据
// oldval如果替换成功，将旧的用户数据地址返回，让用户释放。
// 返回：-1错误，1成功。----------------->如果成功，需要释放旧的用户数据
int rbtreeReplaceOperate(struct rbtreeManagerStruct *rbmng, const void *inkey, int keysize, void *invalue, uint32_t valuesize, void **oldval)
{
    if (!rbmng || !rbmng->cmpfunc)
    {
        logerror("");
        return -1;
    }
    struct rbtreeNodeCommonInform *tempFindData = rbtreeFindNodeCommon(rbmng, inkey, keysize);
    if (tempFindData)
    {
        logwarn("key is in tree, replace it.key=%lu", (uint64_t)inkey);
        if (rbtreeAllocKeyData(tempFindData, inkey, keysize) < 0)
        {
            logerror("rbtreeAllocKeyData alloc error");
            return -1;
        }
        if (oldval)
        {
            oldval[0] = tempFindData->rbval;
        }
        tempFindData->rbval = invalue;
        tempFindData->valsize = valuesize;
        return 1;
    }
    return rbtreeRootInsertCommon(rbmng, inkey, keysize, invalue, valuesize);
}

// 擦除需要返回用户数据，让其释放。
// 查找函数
// inkey:是查找的关键字
// outvalue:返回1时，得到用户数据。
// eraseflag:查找成功，是否从树中删除。1删除，0不删除。
// 返回：-1错误，0没找到，1成功。----------------->eraseflag=1，且成功，需要释放用户数据
int rbtreeFindWithErase(struct rbtreeManagerStruct *rbmng, const void *inkey, int keysize, void **outvalue, uint32_t *outsize, int eraseflag)
{
    if (!rbmng || !rbmng->cmpfunc)
    {
        logerror("");
        return -1;
    }
    struct rbtreeNodeCommonInform *tempFindData = rbtreeFindNodeCommon(rbmng, inkey, keysize);
    return rbtreeGetDataAndEraseCommon(rbmng, tempFindData, outvalue, outsize, eraseflag);
}

// 擦除需要返回用户数据，让其释放。
// 得到根节点数据。
// outvalue:返回1时，得到用户数据。
// eraseflag:操作成功，是否从树中删除。1删除，0不删除。
// 返回：-1错误，0没找到，1成功。eraseflag=1，且成功，需要释放用户数据
int rbtreeGetRootWithErase(struct rbtreeManagerStruct *rbmng, void **outvalue, uint32_t *outsize, int eraseflag)
{
    if (!rbmng || !rbmng->cmpfunc)
    {
        logerror("");
        return -1;
    }
    struct rbtreeNodeCommonInform *tempFindData = rbtreeGetRootInform(rbmng);
    return rbtreeGetDataAndEraseCommon(rbmng, tempFindData, outvalue, outsize, eraseflag);
}

// 擦除需要返回用户数据，让其释放。
// 得到最左节点。
// outvalue:返回1时，得到用户数据。
// eraseflag:操作成功，是否从树中删除。1删除，0不删除。
// 返回：-1错误，0没找到，1成功。----------------->eraseflag=1，且成功，需要释放用户数据
int rbtreeGetLeftesWithErase(struct rbtreeManagerStruct *rbmng, void **outvalue, uint32_t *outsize, int eraseflag)
{
    if (!rbmng || !rbmng->cmpfunc)
    {
        logerror("");
        return -1;
    }
    struct rbtreeNodeCommonInform *tempFindData = rbtreeGetLRLimitInform(rbmng, 1);
    return rbtreeGetDataAndEraseCommon(rbmng, tempFindData, outvalue, outsize, eraseflag);
}

// 擦除需要返回用户数据，让其释放。
// 得到最右节点。
// outvalue:返回1时，得到用户数据。
// eraseflag:操作成功，是否从树中删除。1删除，0不删除。
// 返回：-1错误，0没找到，1成功。----------------->eraseflag=1，且成功，需要释放用户数据
int rbtreeGetRightesWithErase(struct rbtreeManagerStruct *rbmng, void **outvalue, uint32_t *outsize, int eraseflag)
{
    if (!rbmng || !rbmng->cmpfunc)
    {
        logerror("");
        return -1;
    }
    struct rbtreeNodeCommonInform *tempFindData = rbtreeGetLRLimitInform(rbmng, 0);
    return rbtreeGetDataAndEraseCommon(rbmng, tempFindData, outvalue, outsize, eraseflag);
}

static void rbtreeExcuteTraversalFunction(struct rb_node *traversalNode, rbTraversalFunctionType travfunc)
{
    struct rbtreeNodeCommonInform *tempNodeInform = rb_entry(traversalNode, struct rbtreeNodeCommonInform, node);
    if (travfunc && tempNodeInform)
    {
        travfunc(tempNodeInform->rbkey, tempNodeInform->keysize, tempNodeInform->rbval, tempNodeInform->valsize);
    }
}
// traversalflag,0:前序，1：中序，2：后序
static void rbtreeTraversalNode(struct rb_node *traversalNode, rbTraversalFunctionType travfunc, int traversalflag)
{
    if (!traversalNode)
    {
        return;
    }
    if (traversalflag == 0)
    {
        rbtreeExcuteTraversalFunction(traversalNode, travfunc);
    }
    rbtreeTraversalNode(traversalNode->rb_left, travfunc, traversalflag);
    if (traversalflag == 1)
    {
        rbtreeExcuteTraversalFunction(traversalNode, travfunc);
    }
    rbtreeTraversalNode(traversalNode->rb_right, travfunc, traversalflag);
    if (traversalflag == 2)
    {
        rbtreeExcuteTraversalFunction(traversalNode, travfunc);
    }
}
// 遍历二叉树。
// traversalflag,0:前序，1：中序，2：后序
void rbtreeTraversalRoot(struct rbtreeManagerStruct *rbmng, int traversalflag)
{
    rbtreeTraversalNode(rbmng->rbroot.rb_node, rbmng->traversalfunc, traversalflag);
}
